package
{
	import flash.display.Sprite;
	import flash.text.TextField;
	import flash.text.TextFieldAutoSize;

	public class BinaryHeap
	{
		public static const TYPE_MAX:String = 'max';
		public static const TYPE_MIN:String = 'min';
		
		public var type:String;
		public var root:BinaryTreeNode;
		public var nextInsertionNode:BinaryTreeNode;
		public var allNodes:Vector.<BinaryTreeNode>;
		public var numNodes:int;
		
		public function BinaryHeap(type:String = TYPE_MAX)
		{
			this.type = type;
			
			root = new BinaryTreeNode(new BinaryTreeNodeData(int.MIN_VALUE,null));			
			this.nextInsertionNode = root;
			
			this.numNodes = 0;
			this.allNodes = new Vector.<BinaryTreeNode>;
			this.allNodes[numNodes] = root; 
			numNodes++;
		}
		
		public var lastHeight:int = -1;
		public var rowImage:Sprite = new Sprite();
		public function getDrawing():Sprite{
//			var drawing:Sprite = root.getDrawing();
			var drawing:Sprite = new Sprite();
			var i:int = 1;
			for each(var node:BinaryTreeNode in this.allNodes){
				var image:Sprite = new Sprite();
				image.graphics.lineStyle(1);
				image.graphics.drawRect(0,0,20,20);
				image.x = - image.width/2;
				
				var tf:TextField = new TextField();
				if(node.data != null){
					if(node.data.value == int.MIN_VALUE){
						tf.text = '-inf';
					}
					else{
						tf.text = String(node.data.value);
					}
				}
				else{
					tf.text = 'null';
				}
				tf.autoSize = TextFieldAutoSize.LEFT;
				image.addChild(tf);
				//drawing.addChild(image);
				var height:int = (Math.log(i) / Math.log(2));
				if(lastHeight != height){
					rowImage = new Sprite();
					
					drawing.addChild(rowImage);
					rowImage.y = height*image.height;
					lastHeight = height;
				}

				//image.y = height*image.height;
				image.x = (i - Math.pow(2,height)) * 20;

				rowImage.x = -rowImage.width/2;
				rowImage.addChild(image);
				i++;
								
			}
//			updateNodesByDepth();

//			for each(var nodes:Vector.<BinaryTreeNode> in nodesByDepth){
//				
//			}
			return drawing;
		}
		
		public var nodesByDepth:Object;
		public function updateNodesByDepth(node:BinaryTreeNode = null, depth:int = 0):void{
			if(node == null){
				nodesByDepth = new Object();
				updateNodesByDepth(root,0);
			}
			else{
				if(nodesByDepth[depth] == null){
					nodesByDepth[depth] = new Vector.<BinaryTreeNode>;
				}
				
				if(node.left){
					updateNodesByDepth(node.left, depth + 1);
				}
				
				nodesByDepth[depth].push(node);
				
				if(node.right){
					updateNodesByDepth(node.right, depth + 1);
				}
			}
		}
		
		public function insert(num:Number, data:*):void{
			var nodeToInsert:BinaryTreeNode = new BinaryTreeNode(new BinaryTreeNodeData(num, data));
			this.allNodes[this.numNodes] = nodeToInsert;
			this.numNodes++;
			
			nodeToInsert.parent = this.nextInsertionNode;
			
			if(this.nextInsertionNode.left == null){
				this.nextInsertionNode.left = nodeToInsert;
			}
			else 
			if(this.nextInsertionNode.right == null){
				this.nextInsertionNode.right = nodeToInsert;
			}
			else{
				throw new Error("Insertion node is full");
			}
			
			bubbleUp(nodeToInsert);
			
			this.nextInsertionNode = getNextInsertionNode();
		}
		
		
		//		           1
		//	         2            3
		//		 4     5       6      7
		//		8 9   10 11  12  13  14  		
		private function getNextInsertionNode():BinaryTreeNode{
			var height:int = root.getHeight();
			var numNodes:int = this.numNodes;
			if(numNodes == Math.pow(2,height) - 1){
				return getLeftMostLeafNode(root);
			}
			else{
				var index:int = Math.ceil(numNodes/2) - 1;
				return this.allNodes[index];
			}
		}
		
		private function getLeftMostLeafNode(node:BinaryTreeNode):BinaryTreeNode{
			if(node.left == null){
				return node;
			}
			else{
				return getLeftMostLeafNode(node.left);
			}
		}
		
		private function bubbleUp(node:BinaryTreeNode):void{
			if(node.parent == null || node.parent.isNull()){
				return;
			}
			else {
				var parent:BinaryTreeNode = node.parent;
				if(parent.data.value > node.data.value){
					return;
				}
//				else
//				if(parent.data.value == node.data.value){
//					parent.data.appendData(node.data);
//					this.allNodes.pop();
//				}
				else{
					var parentData:BinaryTreeNodeData = parent.data;
					parent.data = node.data;
					node.data = parentData;
					bubbleUp(parent);
				}
			}
		}
		
		
		private function bubbleDown(node:BinaryTreeNode):void{
			var data:BinaryTreeNodeData;
			var nodeToSwap:BinaryTreeNode;
			if(node.left == null && node.right == null){
				return;
			}
			else{
				if(node.left && node.right){
					if(node.left.data.value > node.right.data.value){
						nodeToSwap = node.left;
					}
					else{
						nodeToSwap = node.right;
					}
				}
				else{
					if(node.left){
						nodeToSwap = node.left;
					}
					else{
						nodeToSwap = node.right;
					}

				}
				
				if(nodeToSwap.data.value > node.data.value){
					data = node.data;
					node.data = nodeToSwap.data;
					nodeToSwap.data = data;
					bubbleDown(nodeToSwap);
				}
			}
		}
		
		public function remove():BinaryTreeNode{
			var result:BinaryTreeNode = new BinaryTreeNode(root.data);
			var lastNode:BinaryTreeNode =  this.allNodes[numNodes - 1];
			
			
			root.data = lastNode.data;
			
			if(lastNode.parent.left == lastNode){
				lastNode.parent.left = null;
			}
			else
			if(lastNode.parent.right == lastNode){
				lastNode.parent.right = null;
			}
			
			this.allNodes.pop();
			bubbleDown(root);
				
			this.numNodes--;
			
			return result;
		}
	

		
	}
}